package datastructure.book.dp._1_pathway.exercise.second;

import org.junit.jupiter.api.Test;

public class _7_Solution {
    /**
     * 给你一个 互不相同的整数数组，其中locations[i]表示第i个城市的位置。同时给你start，finish和fuel分别表示出发城市、目的地城市和你初始拥有的汽油总量
     * 每一步中，如果你在城市 i，你可以选择任意一个城市 j，满足 j != i且0 <= j < locations.length，并移动到城市j。从城市i移动到j消耗的汽油量为|locations[i] - locations[j]|，|x|表示x的绝对值。
     * 请注意，fuel任何时刻都不能为负，且你可以经过任意城市超过一次（包括start和finish）。
     * 请你返回从start到finish所有可能路径的数目。
     * 由于答案可能很大， 请将它对10^9 + 7取余后返回。
     * 2 <= locations.length <= 100
     * 1 <= locations[i] <= 109
     * 所有locations中的整数 互不相同。
     * 0 <= start, finish < locations.length
     * 1 <= fuel <= 200
     * 例如：
     * locations = [4,3,1], start = 1, finish = 0, fuel = 6
     * 输出：5
     * 解释：以下为所有可能的路径：
     * 1 -> 0，使用汽油量为 fuel = 1
     * 1 -> 2 -> 0，使用汽油量为 fuel = 5
     * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
     * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
     * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
     * locations = [1,2], start = 1, finish = 1, fuel = 5
     * 输出：3
     * 解释：以下为所有可能的路径：
     * 1(5)
     * 1(5)->0(4)->1(3)
     * 1(5)->0(4)->1(3)->0(2)->1(1)
     */
    public int countRoutes(int[] locations, int start, int finish, int fuel) {
        return 0;
    }

    @Test
    public void test(){
//        int[] loc = {2,3,6,8,4};1,3,5 = 4
        int[] loc = {1,2};
        System.out.println(countRoutes(loc,0,1,5));//3
        System.out.println(countRoutes(loc,1,1,5));//3
        loc = new int[]{2,3,6,8,4};
        System.out.println(countRoutes(loc,1,3,5));// 4
        /**
         * 1(5)
         * 1(5)->0(4)->1(3)
         * 1(5)->0(4)->1(3)->0(2)->1(1)
         *
         * 0(5)->1(4)
         * 0(5)->1(4)->0(3)->1(2)
         * 0(5)->1(4)->0(3)->1(2)->0(1)->1(0)
         * 0,1
         * 1,1
         * 1,2
         * 2,2
         * 2,3
         * 3,3
         */
    }

}
